package day_2022_12_to_3.year2023;

import java.util.Arrays;

/**
 * @author haomin
 * @date 2023/03/23 19:57
 **/
public class Day3_23_Review {
    public static void main(String[] args) {
        int[] arr = new int[]{2,1,123,2,34,3,42,3,4,43,45,4,345,1,2,11,23,34,34,67,4,5,4,9,2,4,3};
//        quickSort(arr, 0, arr.length-1);
//        quickSort1(arr, 0, arr.length-1);
//        quickSort2(arr, 0, arr.length-1);
        quickSort3(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 一路快排
    private static void quickSort(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partiton(arr, l, r);
        quickSort(arr, l, p-1);
        quickSort(arr, p+1, r);
    }

    private static int partiton(int[] arr, int l, int r) {
        int v = arr[l];
        int j = l;
        for(int i = j + 1; i <= r; ++i) {
            if(arr[i] < v) {
                swap(arr , i, j+1);
                j++;
            }
        }
        swap(arr, l, j);
        return j;
    }

    // 二路快排
    private static void quickSort1(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partiton1(arr, l, r);
        quickSort1(arr, l, p-1);
        quickSort1(arr, p+1, r);
    }

    private static int partiton1(int[] arr, int l, int r) {
        int v = arr[l];
        int i = l+1;
        int j = r;
        while(true) {
            while (i <= j && arr[i] < v) {
                i++;
            }
            while (i <= j && arr[j] > v) {
                j--;
            }
            if(i >= j) break;
            swap(arr, i, j);
            i++; j--;
        }
        swap(arr, l, j);
        return j;
    }

    // 挖坑法
    private static void quickSort2(int[] arr, int l, int r) {
        if(l >= r) return;
        int p = partiton2(arr, l, r);
        quickSort2(arr, l, p-1);
        quickSort2(arr, p+1, r);
    }

    private static int partiton2(int[] arr, int l, int r) {
        int i = l;
        int j = r;
        int v = arr[i];
        while(i < j) {
            while (i < j && arr[j] >= v) j--;
            arr[i] = arr[j];
            while (i < j && arr[i] <= v) i++;
            arr[j] = arr[i];
        }
        arr[i] = v;
        return i;
    }

    private static void quickSort3(int[] arr, int l, int r) {
        if(l >= r) return;
        int v = arr[l];
        int lt = l;
        int i = lt+1;
        int gt = r+1;
        while(i < gt) {
            if(arr[i] < v) {
                swap(arr, i, lt+1);
                lt++;
                i++;
            }else if(arr[i] > v) {
                swap(arr, gt-1, i);
                gt--;
            }else i++;
        }
        swap(arr, l, lt);
        quickSort3(arr, l, lt-1);
        quickSort3(arr, gt, r);
    }
}